`:top

In der `F33f`_`[Graphentheorie`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Graphentheorie]`_`f bezeichnet ein `!Prüfer-Code`! eine `F33f`_`[Folge`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Folge_(Mathematik)]`_`f, die einen beschrifteten `F33f`_`[Baum`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Baum_(Graphentheorie)]`_`f `F33f`_`[eineindeutig`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Bijektive_Funktion]`_`f beschreibt. Der Code für einen Baum mit n {\\displaystyle n} `F33f`_`[Knoten`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Knoten_(Graphentheorie)]`_`f hat die Länge n − − 2 {\\displaystyle n-2} und kann mit einem einfachen `F33f`_`[iterativen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Iteration]`_`f `F33f`_`[Algorithmus`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Algorithmus]`_`f erstellt werden. Prüfer-Codes wurden 1918 von `F33f`_`[Heinz Prüfer`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Heinz_Prüfer_(Mathematiker)]`_`f eingeführt, um die `F33f`_`[Cayley-Formel`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Cayley-Formel]`_`f zu beweisen.

>>Contents

• `F0af`_`[Algorithmus`#algorithmus]`_`f

• `F0af`_`[Prüfer-Code aus einem Baum`#pr-fer-code-aus-einem-baum]`_`f

• `F0af`_`[Baum aus einem Prüfer-Code rekonstruieren`#baum-aus-einem-pr-fer-code-rekonstruieren]`_`f

• `F0af`_`[Beispiel`#beispiel]`_`f

• `F0af`_`[Prüfer-Code aus einem Baum`#pr-fer-code-aus-einem-baum]`_`f

• `F0af`_`[Baum aus einem Prüfer-Code`#baum-aus-einem-pr-fer-code]`_`f

• `F0af`_`[Anwendung`#anwendung]`_`f

• `F0af`_`[Literatur`#literatur]`_`f

• `F0af`_`[Weblinks`#weblinks]`_`f

-─

>>Algorithmus

>>>Prüfer-Code aus einem Baum

Erstellt werden kann ein Prüfer-Code aus einem Baum durch das iterative Entfernen von Knoten, bis nur noch zwei Knoten übrig sind. Gegeben sei ein Baum T {\\displaystyle T} mit Knoten { 1 , 2 , … … , n } {\\displaystyle \\{1,2,\\ldots ,n\\}} . Im Schritt i {\\displaystyle i} wird das `F33f`_`[Blatt`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Blatt_(Graphentheorie)]`_`f mit der kleinsten Beschriftung aus dem Baum entfernt und das i {\\displaystyle i} -te Element des Prüfer-Codes auf die Beschriftung des einzigen Nachbarn des entfernten Blattes gesetzt.

Der Code eines Baums ist offensichtlich eindeutig und hat die Länge n − − 2 {\\displaystyle n-2} .

>>>Baum aus einem Prüfer-Code rekonstruieren

Der ursprüngliche Baum aus einem Prüfer-Code kann ebenfalls leicht gewonnen werden.

Dazu geht man den Prüfer-Code p {\\displaystyle p} von links nach rechts durch und schreibt (in eine Liste b {\\displaystyle b} ) die jeweils kleinste Zahl darunter, die weder in p {\\displaystyle p} , noch in b {\\displaystyle b} enthalten ist. Diese wird mit der aktuellen Zahl in p {\\displaystyle p} verbunden. Die aktuelle Zahl in p {\\displaystyle p} wird anschließend gestrichen. Diese Schritte werden wiederholt, bis keine Elemente mehr in p {\\displaystyle p} vorhanden sind. Das i {\\displaystyle i} -te Element in p {\\displaystyle p} ist dann jeweils mit dem i {\\displaystyle i} -ten Element in b {\\displaystyle b} durch eine Kante verbunden.

Man erhält so allerdings einen Baum mit nur n − − 1 {\\displaystyle n-1} Knoten. Um den n {\\displaystyle n} -ten Knoten zu erhalten, verbindet man nun die zwei Zahlen, die nicht in b {\\displaystyle b} enthalten sind, durch eine weitere Kante.

>>Beispiel

>>>Prüfer-Code aus einem Baum

Der oben vorgestellte Algorithmus wird auf das Bild rechts angewandt. Zu Beginn ist der Knoten 1 das Blatt mit der kleinsten Beschriftung, daher wird dieser Knoten als erstes entfernt und 5 wird als erstes Element in den Prüfer-Code eingefügt. Anschließend werden die Blätter 3 und 4 aus dem Baum entfernt und die Folge um 5 und 2 erweitert. Da der Knoten 5 jetzt das kleinste Blatt ist, wird er aus dem Baum entfernt und 2 an die Folge angehängt. Als letzter Knoten wird Knoten 6 aus dem Baum entfernt und 2 an die Folge angehängt. Der Algorithmus terminiert, da nur noch zwei Knoten (2 und 7) übrig sind.

>>>Baum aus einem Prüfer-Code

Wir verwenden den obigen Prüfer-Code p = ( 5 , 5 , 2 , 2 , 2 ) {\\displaystyle p=(5,5,2,2,2)} .

1. Das kleinste Element, das nicht in p {\\displaystyle p} oder in b = ( ) {\\displaystyle b=()} enthalten ist, ist 1. Die erste 5 wird also im Baum mit der 1 verbunden, die 1 zu b {\\displaystyle b} hinzugefügt und die 5 gestrichen.

2. Das kleinste Element, das nicht in p = ( 5 , 2 , 2 , 2 ) {\\displaystyle p=(5,2,2,2)} oder in b = ( 1 ) {\\displaystyle b=(1)} enthalten ist, ist die 3. Es folgt: p = ( 2 , 2 , 2 ) {\\displaystyle p=(2,2,2)} , b = ( 1 , 3 ) {\\displaystyle b=(1,3)} und die 5 und die 3 werden im Baum durch eine Kante verbunden.

3. Als nächstes ist 4 das kleinste Element, das nicht in p {\\displaystyle p} oder b {\\displaystyle b} liegt. Es folgt: p = ( 2 , 2 ) {\\displaystyle p=(2,2)} , b = ( 1 , 3 , 4 ) {\\displaystyle b=(1,3,4)} und die 2 und die 4 werden im Baum durch eine Kante verbunden.

4. Als nächstes ist 5 das kleinste Element, das nicht in p {\\displaystyle p} oder b {\\displaystyle b} liegt. Es folgt: p = ( 2 ) {\\displaystyle p=(2)} , b = ( 1 , 3 , 4 , 5 ) {\\displaystyle b=(1,3,4,5)} und die 2 und die 5 werden im Baum durch eine Kante verbunden.

5. Als nächstes ist 6 das kleinste Element, das nicht in p {\\displaystyle p} oder b {\\displaystyle b} liegt. Es folgt: p = ( ) {\\displaystyle p=()} , b = ( 1 , 3 , 4 , 5 , 6 ) {\\displaystyle b=(1,3,4,5,6)} und die 2 und die 6 werden im Baum durch eine Kante verbunden.

6. Der Baum mit n − − 1 {\\displaystyle n-1} Knoten ist nun fertiggestellt. Da der Prüfer-Code fünfstellig ist, fehlt noch ein Knoten. Dieser ergibt sich, indem die beiden Zahlen, die jetzt nicht in b = ( 1 , 3 , 4 , 5 , 6 ) {\\displaystyle b=(1,3,4,5,6)} enthalten sind (also 2 und 7) verbunden werden.

>>Anwendung

Der Prüfer-Code eines Baums mit n {\\displaystyle n} Knoten ist eine eindeutige Folge der Länge n − − 2 {\\displaystyle n-2} mit Elementen aus { 1 , … … , n } {\\displaystyle \\{1,\\ldots ,n\\}} . Umgekehrt gilt, dass es zu einem gegebenen Prüfer-Code S {\\displaystyle S} der Länge n − − 2 {\\displaystyle n-2} mit Elementen aus { 1 , … … , n } {\\displaystyle \\{1,\\ldots ,n\\}} einen eindeutigen beschrifteten Baum gibt. Das kann einfach mittels `F33f`_`[Induktion`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Vollständige_Induktion]`_`f über n {\\displaystyle n} gezeigt werden.

Die direkte Konsequenz daraus ist, dass Prüfer-Codes eine `F33f`_`[Bijektion`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Bijektion]`_`f zwischen der Menge der beschrifteten Bäume mit n {\\displaystyle n} Knoten und der Menge der Folgen der Länge n − − 2 {\\displaystyle n-2} mit Elementen aus { 1 , … … , n } {\\displaystyle \\{1,\\ldots ,n\\}} darstellen. Die letztgenannte Menge hat die Größe n n − − 2 {\\displaystyle n^{n-2}} , wodurch die Existenz der Bijektion die `F33f`_`[Cayley-Formel`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Cayley-Formel]`_`f beweist: Es gibt n n − − 2 {\\displaystyle n^{n-2}} beschriftete Bäume mit n {\\displaystyle n} Knoten.

Die Ergebnisse können verallgemeinert werden: Ein beschrifteter Baum ist ein `F33f`_`[Spannbaum`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Spannbaum]`_`f eines beschrifteten `F33f`_`[vollständigen Graphen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Vollständiger_Graph]`_`f. Werden geeignete Einschränkungen an den Prüfer-Code gestellt, kann mit ähnlichen Methoden die Anzahl von Spannbäumen für vollständige bipartite Graphen ermittelt werden. Ist G {\\displaystyle G} ein vollständiger `F33f`_`[bipartiter Graph`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Bipartiter_Graph]`_`f mit Knoten 1 {\\displaystyle 1} bis k {\\displaystyle k} in einer Partition und Knoten k + 1 {\\displaystyle k+1} bis n {\\displaystyle n} in der anderen Partition, so ist in G {\\displaystyle G} die Anzahl der beschrifteten Spannbäume k n − − k − − 1 ( n − − k ) k − − 1 {\\displaystyle k^{n-k-1}(n-k)^{k-1}} .

>>Literatur

• Heinz Prüfer: `*Neuer Beweis eines Satzes über Permutationen.`* In: `*`F33f`_`[Archiv der Mathematik und Physik`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Archiv_der_Mathematik_und_Physik]`_`f.`* Reihe 3, Bd. 27, 1918, S. 742–744.

>>Weblinks

Commons

: Prüfer-Code

– Sammlung von Bildern, Videos und Audiodateien

`c`F0af`_`[↑ Back to top`#top]`_`f`a